This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present invention that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.
An online/offline signature scheme allows a two-phase generation of a digital signature. The most costly computations may be performed before the message to sign is known; this is the offline phase. Once the message is known, relatively rapid computations are then performed in the online phase. The skilled person will appreciate that this property is desired for time-constrained applications, such as for example electronic payments or when driving towards automated toll booths, and also for low-cost devices that do not have much in the way of computational resources.
In “On the Fly Authentication and Signature Schemes Based On Groups of Unknown Order” Journal of Cryptology, 19(4):463-487, 2006, M. Girault, G. Poupard, and J. Stern propose an online/offline signature scheme known as the GPS scheme. A drawback of this scheme is that its security proof stands in the random oracle model.
An online/offline signature scheme in the standard model (i.e. not relying on random oracles) is presented by B. Chevallier-Mames and M. Joye in “A Practical and Tightly Secure Signature Scheme Without Hash Function” in M. Abe (editor), Topics in Cryptology—CT-RSA 2007, volume 4377 of Lecture Notes in Computer Science, pages 339-356, Springer-Verlag, 2007. A drawback of this scheme resides in the size of its parameters, the public and private keys, as well as in the size of the resulting signature (both in the off-line and on-line phases). Further, it is noted that an increased size translates into an efficiency loss in computation, storage and transmission.
Another on-line/off-line signature scheme in the standard model is presented by K. Kurosawa and K. Schmidt-Samoa in “New On-line/Off-line Signature Schemes Without Random Oracles” in M. Yung et al. (editors), Public Key Cryptography—PKC 2006, volume 3958 of Lecture Notes in Computer Science, pages 330-346, Springer-Verlag, 2006. A drawback in this scheme is that the on-line phase involves a modular multiplication, which is more costly than an integer multiplication.
Further on-line/off-line signature schemes are presented by Marc Joye and Hung-Mei Lin in “On the TYS Signature Scheme”. These schemes are the Tan-Yi-Siew (TYS) signature scheme in its original and in its modified form.
The original TYS scheme first generates a public key and a private key. Two random primes are chosen p=2p′+1 and q=2q′+1, where p′ and q′ are prime and log2p′q′>2I+1. N=pq. Two quadratic residues g and x in Z*N are chosen such that the order of g is p′q′. Finally, a random I-bit integer z is chosen and h=g−z mod N is calculated. The public key is pk={g, h, x, N} and the private key is sk={p, q, z}. m denotes the message to be signed. An I-bit integer k and an I-bit prime e are randomly picked and the following values are computed: y=(xg−k)1/e mod N, c=H(pk, y, m) and t=k+cz. The signature on message m is then σ=(t, y, e). The authors discovered however that the TYS scheme was totally insecure and therefore provided a modified scheme.
The modified scheme makes use of four security parameters—IN, IH, IE and IK —that satisfy IE≧IH+2 and IK>>IN+IH. The modified scheme first generates a public key and a private key. Two random primes are chosen p=2p′+1 and q=2q′+1, where p′ and q′ are primes of equal length so that N=pq is of length IN. Two quadratic residues g and x in Z*N are chosen randomly. Finally, h=g−z mod N is calculated for a random integer z mod p′q′. The public key is still pk={g, h, x, N} and the private key is sk={p, q, z}. m denotes the message to be signed. An IK-bit integer t and an IE-bit prime e are randomly picked and the following values are computed: y=(xg−t)1/e mod N, c=H(pk, m) and k=t+cz. The signature on message m is then σ=(k, y, e). As will be appreciated, it is mainly the lengths of some parameters that have changed, but this does in fact provide the security that the TYS scheme lacks. However, the modified scheme, which may be seen as a variant of the Camenisch-Lysyanskaya signature scheme, still requires rather much computation and provides a quite lengthy signature. For example, typical parameter lengths—IN=1024, IH=160, IE=162 and IK=1344—give a signature length of 1344+1024+162=2530 bits for the 1024-bit RSA modulus.
It can therefore be appreciated that there is a need for an improved solution that provides online/offline digital signatures. This invention provides such a solution.